import org.junit.Assert
import org.junit.Test

class Test2 {
    @Test
    fun test1() {
//        Assert.assertEquals(expected, actual)
        val list = MyLinkedList()

        Assert.assertEquals("", getActual(list.dummyHeader))

        list.addAtHead(1)
        Assert.assertEquals("1,", getActual(list.dummyHeader))

        list.addAtTail(3)
        Assert.assertEquals("1,3,", getActual(list.dummyHeader))

        list.addAtIndex(1, 2)
        Assert.assertEquals("1,2,3,", getActual(list.dummyHeader))

        val value = list.get(1)
        Assert.assertEquals(2, value)
        Assert.assertEquals("1,2,3,", getActual(list.dummyHeader))

        list.deleteAtIndex(1)
        Assert.assertEquals("1,3,", getActual(list.dummyHeader))

        val value2 = list.get(1)
        Assert.assertEquals(3, value2)
        Assert.assertEquals("1,3,", getActual(list.dummyHeader))

        val value3 = list.get(3)
        Assert.assertEquals(-1, value3)
        Assert.assertEquals("1,3,", getActual(list.dummyHeader))
    }

    @Test
    fun test2() {
//        Assert.assertEquals(expected, actual)
        val list = MyLinkedList()

        Assert.assertEquals("", getActual(list.dummyHeader))

        list.get(1)
        Assert.assertEquals("", getActual(list.dummyHeader))
    }

    @Test
    fun test3() {
//        Assert.assertEquals(expected, actual)
        val list = MyLinkedList()

        Assert.assertEquals("", getActual(list.dummyHeader))

        list.addAtIndex(1, 1)
        Assert.assertEquals("1,", getActual(list.dummyHeader))

        val value = list.get(0)
        Assert.assertEquals(1, value)
        Assert.assertEquals("1,", getActual(list.dummyHeader))
    }

    @Test
    fun test4() {
//        Assert.assertEquals(expected, actual)
        val list = MyLinkedList()

        Assert.assertEquals("", getActual(list.dummyHeader))

        list.addAtIndex(0, 1)
        Assert.assertEquals("1,", getActual(list.dummyHeader))
        list.addAtIndex(1, 0)
        Assert.assertEquals("1,0,", getActual(list.dummyHeader))

        val value = list.get(1)
        Assert.assertEquals(0, value)
        Assert.assertEquals("1,0,", getActual(list.dummyHeader))
    }

    @Test
    fun test5() {
//        Assert.assertEquals(expected, actual)
        val list = MyLinkedList()

        Assert.assertEquals("", getActual(list.dummyHeader))

        list.addAtIndex(1, 0)
        Assert.assertEquals("0,", getActual(list.dummyHeader))

        val value = list.get(1)
        Assert.assertEquals(-1, value)
        Assert.assertEquals("0,", getActual(list.dummyHeader))

        val value2 = list.get(0)
        Assert.assertEquals(0, value2)
        Assert.assertEquals("0,", getActual(list.dummyHeader))
    }

    private fun getActual(node: ListNode?): String {
        var s: String = ""
        var p: ListNode? = node?.next
        while (p != null) {
            s = s + p.`val` + ","
            p = p.next
        }
        return s
    }

    //    class MyLinkedList {
//        // 单链表
//        val dummyHeader = ListNode(0)
//        var size: Int = 0
//
//        class ListNode(val `val`: Int) {
//            var next: ListNode? = null
//        }
//
//        fun get(index: Int): Int {
//            var currentIndex: Int = -1
//            var p: ListNode? = dummyHeader
//            while (true) {
//                if (null == p) {
//                    break
//                }
//                p = p.next
//                currentIndex++
//                if (currentIndex == index) {
//                    if (null == p) {
//                        return -1
//                    }
//                    return p.`val`
//                }
//                if (currentIndex >= size - 1) {
//                    return -1
//                }
//            }
//            return currentIndex
//        }
//
//        fun addAtHead(`val`: Int) {
//            val node = ListNode(`val`)
//            val head = dummyHeader.next
//            if (head == null) {
//                dummyHeader.next = node
//            } else {
//                dummyHeader.next = node
//                node.next = head
//            }
//            size = size + 1
//        }
//
//        fun addAtTail(`val`: Int) {
//            val node = ListNode(`val`)
//            var p: ListNode? = dummyHeader
//            // find the end
//            while (p?.next != null) {
//                p = p.next
//            }
//            p?.next = node
//            size = size + 1
//        }
//
//        fun addAtIndex(index: Int, `val`: Int) {
//            // index >= end index , add to tail
//            // index = 0,  add to head
//            // add to index
//            val endIndex = size - 1
//
//            if (endIndex < 0 || index == 0) {
//                addAtHead(`val`)
//                return
//            }
//            if (index > endIndex) {
//                addAtTail(`val`)
//                return
//            } else {
//                // add to index
//                var left: ListNode? = dummyHeader
//                var currentIndex = -1
//                var right: ListNode? = null
//                while (left != null) {
//                    right = left.next
//                    currentIndex++
//                    if (currentIndex == index) {
//                        // insert
//                        val node = ListNode(`val`)
//                        node.next = right
//                        left.next = node
//                        size++
//                        break
//                    }
//                    left = left.next
//                }
//            }
//        }
//
//        fun deleteAtIndex(index: Int) {
//            var currentIndex: Int = -1
//            var left: ListNode? = dummyHeader
//            var right: ListNode?
//            while (left != null) {
//                right = left.next
//                currentIndex++
//                if (right == null) {
//                    break
//                }
//                if (index == currentIndex) {
//                    // remove
//                    val next = right.next
//                    left.next = next
//                    size = size - 1
//                    break
//                }
//                left = right
//            }
//        }
//    }
// 单链表
    class MyLinkedList {
        val dummyHeader = ListNode(0)
        var size: Int = 0

        fun get(index: Int): Int {
            if (index < 0 || index > size - 1) {
                return -1
            }
            var p: ListNode? = dummyHeader
            for (i in 0..index) { // [0,index]
                p = p?.next
            }
            if (p == null) {
                return -1
            }
            return p.`val`
        }

        fun addAtHead(`val`: Int) {
            addAtIndex(0, `val`)
        }

        fun addAtTail(`val`: Int) {
            addAtIndex(size, `val`)
        }

        fun addAtIndex(index: Int, `val`: Int) {
            if (index > size) {
                return
            }

            size++
            // find the prev
            val prev: ListNode? = findPrev(Math.max(0, index))
            // prev -> next
            // prev -> data -> next
            add(prev, `val`)
        }

        private fun add(prev: ListNode?, `val`: Int) {
            val next: ListNode? = prev?.next
            val node: ListNode = ListNode(`val`)
            node.next = next
            prev?.next = node
        }

        // 找出要删除或插入位置到前一个节点
        private fun findPrev(index: Int): ListNode? {
            // find the prev
            var prev: ListNode? = dummyHeader
            for (i in 0..index - 1) { // [0,index-1], prev = index -1
                prev = prev?.next
            }
            return prev
        }

        fun deleteAtIndex(index: Int) {
            if (index < 0 || index > size - 1) {
                return
            }
            size -= 1
            // find the prev
            val prev: ListNode? = findPrev(index)
            // prev -> data -> next
            // prev -> next
            delete(prev)
        }

        private fun delete(prev: ListNode?) {
            val next: ListNode? = prev?.next?.next
            prev?.next = next
        }
    }

}